

_end = '_end_'


# to search if a word in trie
def in_trie(trie, word):
    current_dict = trie
    for letter in word:
        if letter in current_dict:
            current_dict = current_dict[letter]
        else:
            return False
    else:
        if _end in current_dict:
            return True
        return False


# create trie shoted with word
def create_trie(*words):
    root = dict()
    for word in words:
        current_dict = root
        for letter in word:
            current_dict = current_dict.setdefault(letter, {})
        current_dict = current_dict.setdefault(_end, _end)
    return root


def insert_word(trie, word):
    if in_trie(trie, word):
        return

    current_dict = trie
    for letter in word:
        current_dict = current_dict.setdefault(letter, {})
    current_dict = current_dict.setdefault(_end, _end)


def remove_word(trie, word):
    current_dict = trie
    for letter in word:
        current_dict = current_dict.get(letter, None)
        if current_dict is None:
            break
    else:
        del current_dict[_end]


dict = create_trie('foo', 'bar', 'baz', 'bar')
print(dict)
print(in_trie(dict, 'bar'))
print(in_trie(dict, 'bars'))
insert_word(dict, 'bars')
print(dict)
print(in_trie(dict, 'bars'))
